package 算法基础模板.chapter_04;

import java.util.*;

/**
 * 求约数
 *
 * @author Summerday
 */
public class DivisorT {

    public static void main (String[] args) {

        List<Integer> divisors = new DivisorT().getDivisors(20);
        long cnt = new DivisorT().getCnt(20);
        long sum = new DivisorT().getSum(20);

        System.out.println(divisors);
        System.out.println(cnt);
        System.out.println(sum);
    }

    // 试除法求约数
    List<Integer> getDivisors (int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i <= n / i; i++) {
            if (n % i == 0) {
                res.add(i);
                if (i != n / i) res.add(n / i); // 边界情况, i == n / i 只需要加1个
            }
        }
        Collections.sort(res);
        return res;
    }

    // 求约数个数
    long getCnt (int x) {
        Map<Integer, Integer> primes = new HashMap<>();
        for (int i = 2; i <= x / i; i++) {
            while (x % i == 0) {
                x /= i;
                primes.put(i, primes.getOrDefault(i, 0) + 1);
            }
        }
        if (x > 1) primes.put(x, primes.getOrDefault(x, 0) + 1);
        System.out.println(primes);
        int mod = 1000000007;
        long res = 1;
        for (int key : primes.keySet()) {
            res = res * (primes.get(key) + 1) % mod;
        }
        return res;
    }

    // 求约数之和
    long getSum (int x) {
        Map<Integer, Integer> primes = new HashMap<>();
        for (int i = 2; i <= x / i; i++) {
            while (x % i == 0) {
                x /= i;
                primes.put(i, primes.getOrDefault(i, 0) + 1);
            }
        }
        if (x > 1) primes.put(x, primes.getOrDefault(x, 0) + 1);
        int mod = 1000000007;
        long res = 1;
        for (int key : primes.keySet()) {
            int p = key, a = primes.get(key);
            long t = 1;
            while (a-- > 0) t = (t * p + 1) % mod;
            res = res * t % mod;
        }
        return res;
    }

    // 求最大公约数
    int gcd (int a, int b) {
        return b > 0 ? gcd(b, a % b) : a;
    }

}
